package com.analysis.service.impl;

public class DTW {

    public static void main(String[] args) {
        double[] a = { 3, 1, 20 };
        double[] b = { 3, 3, 1, 1, 20 };
        dtw(a, b);
    }

    public static double Min(double a1, double b1) {
        return a1 < b1 ? a1 : b1;
    }

    public static double dtw(double[] a, double[] b) {
        int N = a.length;
        int M = b.length;
        int i, j;

        double[][] distance = new double[N + 1][M + 1];
        double[][] output = new double[N + 1][M + 1];

        for (i = 1; i <= N; i++) {
            for (j = 1; j <= M; j++) {
                distance[i][j] = Math.abs(b[j - 1] - a[i - 1]);
            }
        }

        for (i = 1; i <= N; i++) {
            for (j = 1; j < M; j++) {
                output[i][j] = Min(Min(output[i - 1][j - 1], output[i][j - 1]), output[i - 1][j]) + distance[i][j];
            }
        }

        return output[N][M - 1];
    }
}
